package org.chengn.level_hard.context2132;

/**
 * @Title: Context2132
 * @Author ChengN
 * @Package org.chengn.level_hard.context2132
 * @Date 2023/12/15 0:31
 * @description: 用邮票贴满网格图
 */
public class Context2132 {
    public boolean possibleToStamp(int[][] grid, int stampHeight, int stampWidth) {
        int row = grid.length, col = grid[0].length;

        int[][] sums = new int[row + 1][col + 1];

        // 计算前缀和
        for (int i = 1; i <= row; ++i) {
            for (int j = 1; j <= col; ++j) {
                sums[i][j] = sums[i - 1][j] + sums[i][j - 1] - sums[i - 1][j - 1] + grid[i - 1][j - 1];
            }
        }

        // 计算二维差分，即每个点是否被贴上邮票
        int[][] dist = new int[row + 2][col + 2];
        for (int i = stampHeight; i <= row; ++i) {
            for (int j = stampWidth; j <= col; ++j) {
                if (sums[i][j] - sums[i - stampHeight][j] -
                        sums[i][j - stampWidth] +
                        sums[i - stampHeight][j - stampWidth] == 0) {
                    dist[i - stampHeight + 1][i - stampWidth + 1]++;
                    dist[i + 1][j + 1]++;
                    dist[i - stampHeight + 1][j + 1]--;
                    dist[i + 1][j - stampWidth + 1]--;
                }
            }
        }

        for (int i = 1; i <= row; ++i) {
            for (int j = 1; j <= col; ++j) {
                if (grid[i - 1][j - 1] == 0 && dist[i][j] - dist[i - 1][j] - dist[i][j - 1] + dist[i - 1][j - 1] == 0) {
                    return false;
                }
            }
        }
        return true;

    }
}
